package com.changanw.code31;

import java.util.Arrays;

/**
 * @author changanw
 * @description   数组的下一个排列，给定一个长度的数组，该数组会有一个全排列，也就是给定其中的一个排列，得出下一个排列。如果给定的是
 * 最大的一个排列，那么下一个排列就是最小的排列
 * @date 2023/7/17 13:24
 */
public class Code31 {
  public void nextPermutation(int[] nums) {
    //从后向前遍历数组
    for (int i = nums.length -1;i >= 0;i--){
      for (int j = nums.length -1;j > i;j--){
        //如果发现前一个数比后一个数小，则交换两个数的位置，然后对i位置以后得数进行一个升序排序
        int num = nums[i];
        int num1 = nums[j];
        if (num < num1){
          swap(nums,i,j);
          Arrays.sort(nums,i+1,nums.length);
          return;
        }
      }
    }
    Arrays.sort(nums);
  }

  /**
   * 交换数组中两个元素的位置
   * @param nums
   * @param i
   * @param j
   */
  public void swap(int[] nums,int i,int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }

  public static void main(String[] args) {
    Code31 code31 = new Code31();
    int[] nums = {1,2,3,5,4};
    //int[] nus = new int[]{111};
    //
    int[] nus = new int[3];
    code31.nextPermutation(nums);
    System.out.println(Arrays.toString(nums));
  }
}
